Graph pattern matching, also known as “subgraph isomorphism,” is becoming a problem of significant interest, as the growth in graph databases has increased. It is important to use a fast solution to this problem, which involves finding all (or some) subgraphs of a graph D (the data graph) that are isomorphic to another graph Q (the query graph). Although the general problem of subgraph isomorphism is NP-Hard (“Non-deterministic Polynomial-time hard”), the actual instances of this problem are tractable in practical contexts, because nodes and edges are associated with unique identifiers and/or a set of properties in popular graph data models.
Multiple solutions have been proposed for subgraph isomorphism. In one solution, a graph database adopts the classic RDF graph data model and SPARQL, a query language for RDF data. When a SPARQL query is submitted, an RDF database finds all matching subgraphs and graph elements of the query, by solving the subgraph isomorphism problem. Similar pattern-matching operations are also supported by graph databases that adopt the more recent Property Graph (PG) data model. Noticeably, these graph databases are all based on secondary storage so that they can process very large graphs. However, such secondary storage based solutions are much slower than in-memory solutions due to the huge overhead from the storage layer.
In contrast, in-memory solutions exist for this problem. However, most of these solutions are single-threaded and are not easily parallelizable due to their respective complexity. In addition, these solutions do not handle large-sized graphs very well on shared-memory multi-processor systems because those solutions rely on data representations that have large memory footprints.
The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.